package com.south.base.test.arithmetic;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;
import java.util.List;

/**
 * 接龙游戏
 *
 * @author Administrator
 * @date 2020/8/28 10:45
 */
public class SolitaireGame {

    /**
     * TODO 单词接龙
     * 给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
     * 每次转换只能改变一个字母。
     * 转换过程中的中间单词必须是字典中的单词。
     * 说明:
     * 如果不存在这样的转换序列，返回 0。
     * 所有单词具有相同的长度。
     * 所有单词只由小写字母组成。
     * 字典中不存在重复的单词。
     * 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
     */
    @Test
    public void ladderLength() {
        Assert.assertEquals(5, ladderLength("hit", "cog", Arrays.asList("hot", "dot", "dog", "lot", "log", "cog")));
        Assert.assertEquals(0, ladderLength("hit", "cog", Arrays.asList("hot", "dot", "dog", "lot", "log")));
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) {
            return 0;
        }
        int[] dp = new int[wordList.size()];
        dfs(dp, endWord, wordList);
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < dp.length; i++) {
            if (beginWord.equals(wordList.get(i))) {
                min = Math.min(min, dp[i]);
                continue;
            }
            if (!isDif(beginWord, wordList.get(i))) {
                continue;
            }
            min = Math.min(min, dp[i] + 1);
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }

    public void dfs(int[] dp, String endWord, List<String> wordList) {
        for (int i = 0; i < wordList.size(); i++) {
            if (!isDif(endWord, wordList.get(i)) || endWord.equals(wordList.get(i))) {
                continue;
            }
            dp[i] = Math.min(dp[i], dp[wordList.indexOf(endWord)] + 1);
            dfs(dp, wordList.get(i), wordList);
        }
    }

    public boolean isDif(String beginWord, String endWord) {
        if (beginWord.length() != endWord.length()) {
            return false;
        }
        int dif = 0;
        for (int i = 0; i < beginWord.length(); i++) {
            dif += beginWord.charAt(i) == endWord.charAt(i) ? 0 : 1;
        }
        return dif == 1;
    }
}
